package leetcode100

// TODO 深度优先搜索 [经典] 【-】 岛屿数量
// TODO https://leetcode.cn/problems/number-of-islands/solution/dfs-by-wwsw-kjwp/

func numIslands(grid [][]byte) (ans int) {
	m, n := len(grid), len(grid[0])

	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || r >= m || c < 0 || c >= n {
			return
		} // 递归终止条件：越界（无效的网格），则返回
		if grid[r][c] != '1' {
			return
		} // 非未访问过的陆地（水or已访问过的陆地），则返回
		grid[r][c] = '2' // 标记已访问过的陆地：防止无限循环无法退出
		dfs(r-1, c)
		dfs(r+1, c)
		dfs(r, c-1)
		dfs(r, c+1)
	}

	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == '1' { // 遇到一个陆地，结果+1，并则将其周围四个相连的陆地变为非陆地
				ans++
				dfs(r, c)
			}
		}
	}
	return
}
